class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        pre = ans = 0
        for x in nums:
            pre += x
            tmp = pre % k
            if tmp == 0:
                ans += 1
            ans += cnt[tmp]
            cnt[tmp] += 1
        return ans
